# 429.N叉树的层序遍历
# 给定一个N叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。树的序列化输入是用层序遍历，每组子节点都由null值分隔（参见示例）。
#
#
# 示例1：
# 输入：root = [1, null, 3, 2, 4, null, 5, 6]
# 输出：[[1], [3, 2, 4], [5, 6]]
#
#
# 示例2：
# 输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
# 输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]


class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children

class Solution:
    def levelOrder(self, root:'Node'):
        from collections import deque
        que = deque()
        res = []
        if not root:
            return res
        que.append(root)
        while que:
            size = len(que)
            tmp = []
            for i in range(size):
                node = que.popleft()
                tmp.append(node.val)
                # 看了一眼其他人的答案，如果有chidren，直接extend children就行
                # if node.children:
                #     que.extend(node.children)
                c_zise = len(node.children)
                for i in range(c_zise):
                    que.append(node.children[i])
            res.append(tmp)
        return res


if __name__ == '__main__':
    a32 = Node(7)
    a31 = Node(15)
    a21 = Node(9)
    a22 = Node(20,a31)
    a11 = Node(3,a21)
    tmp = Solution2()
    res = tmp.levelOrder(a11)
    print(res)
    #我看了一下，我的答案和extend的写法都可以在leetcode上面通过，但是无法在pycharm上面验证
